package com.chenxys.algorithm.leetcode;

import com.chenxys.algorithm.common.ArrUtils;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>
 *      leetCode第一题<br/>
 *      给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
 *      你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。<br/>
 *      输入：nums = [2,7,11,15], target = 9<br/>
 *      输出：[0,1]<br/>
 *      解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。<br/>
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.leetcode
 * @Copyright ©
 */
@SuppressWarnings("all")
public class LeetCode01 {
    // 使用hash表,先查询hash表中是否存在target - [i]的值,如果存在,返回。不存在,将当前位置的值放入hash表,若遍历完数组依旧不存在,返回空数组
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) return new int[]{i, map.get(target - nums[i])};
            map.put(nums[i], i);
        }
        return new int[0];
    }

    public static int[] twoSumV2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int tmp = target - nums[i];
            if (map.containsKey(tmp)) return new int[]{i, map.get(tmp)};
            map.put(nums[i], i);
        }
        return null;
    }

    /**
     * <p>
     *     检查获取的是否正确
     * </p>
     * @param nums 待相加元数组
     * @param target 获取下标的数组
     * @param sum 两数和
     * @return 是否为两数和
     */
    public static boolean checkTwoSum(int[] nums, int[] target, int sum){
        if ((nums == null || nums.length < 2) || (target == null || target.length != 2)) return true;
        return sum == nums[target[0]] + nums[target[1]];
    }

/*    // 对数器
    public static int[] generateRandomArr(int maxSize, int maxValue) {
        int len = (int) ((Math.random()) * (maxSize + 1));
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = (int) ((Math.random()) * (maxValue + 1));
        }
        return arr;
    }*/


    public static void main(String[] args) {
        int maxSize = 50;
        int maxValue = 100;
        int testTimes = 100000;
        System.out.println("Test Begin!");
        for (int i = 0; i < testTimes; i++) {
            int target = (int) ((Math.random()) * (maxValue + 1));
//            int[] ints = generateRandomArr(maxSize, maxValue);
            int[] ints = ArrUtils.generateRandomArr(maxSize, maxValue);
            int[] ans = twoSum(ints, target);
            if (!checkTwoSum(ints, ans, target)) {
                System.out.println("Oops!");
            }
        }
        System.out.println("Test Finish!");
    }
}
